package com.li.list;

public class 两个链表的第一个公共结点 {
	public static void main(String[] args) {
		Node head = new Node();
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);

		head.next = node1;
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		
		Node head2 = new Node();
		Node node21 = new Node(1);
		Node node22 = new Node(2);
		Node node23 = new Node(3);
		

		head2.next = node21;
		node21.next = node22;
		node22.next = node23;
		node23.next = node4;
		
		System.out.println(findFirstCommonNodeII(head,head2).value);
		
	}

	/**
	 * 两个链表，找第一个公共节点
	 * @param pHead1
	 * @param pHead2
	 * @return
	 */
	public static Node findFirstCommonNodeII(Node pHead1, Node pHead2) {
        Node current1 = pHead1;// 链表1
        Node current2 = pHead2;// 链表2
        if (pHead1 == null || pHead2 == null)
            return null;
        int length1 = getLength(current1);
        int length2 = getLength(current2);
        // 两连表的长度差
         
        // 如果链表1的长度大于链表2的长度
        if (length1 >= length2) {
            int len = length1 - length2;
            // 先遍历链表1，遍历的长度就是两链表的长度差
            while (len > 0) {
                current1 = current1.next;
                len--;
            }
 
        }
        // 如果链表2的长度大于链表1的长度
        else if (length1 < length2) {
            int len = length2 - length1;
            // 先遍历链表1，遍历的长度就是两链表的长度差
            while (len > 0) {
                current2 = current2.next;
                len--;
            }
 
        }
        //开始齐头并进，直到找到第一个公共结点
        while(current1!=current2){
            current1=current1.next;
            current2=current2.next;
        }
        return current1;
 
    }
 
    // 求指定链表的长度
    public static int getLength(Node pHead) {
        int length = 0;
 
        Node current = pHead;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }
}
